package leetcode.code2033;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int minOperations(int[][] grid, int x) {
		int m = grid.length, n = grid[0].length;
		int size = m * n;
		int[] nums = new int[size];
		int p = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				nums[p++] = grid[i][j];
			}
		}
		return this.minMoves2(nums, x);
	}

	public int minMoves2(int[] nums, int x) {
		int len = nums.length;
		int k = (len & 1) == 0 ? len >> 1 : (len >> 1) + 1;
		int mid = this.kthLargestNumber(nums, k);
		int ans = 0;
		for (int i = 0; i < nums.length; i++) {
			int dif = Math.abs(mid - nums[i]);
			if ((dif % x) != 0) {
				return -1;
			}
			ans += dif / x;
		}
		return ans;
	}

	public int kthLargestNumber(int[] nums, int k) {
		return kthLargestNumber(nums, 0, nums.length - 1, k);
	}

	private int kthLargestNumber(int[] nums, int L, int R, int k) {
		int randomIndex = (int) (Math.random() * (R - L + 1)) + L;
		int index = this.sort(nums, L, R, randomIndex);
		if (index == k - 1) {
			return nums[index];
		} else if (index < k - 1) {
			return this.kthLargestNumber(nums, index + 1, R, k);
		} else {
			return this.kthLargestNumber(nums, L, index - 1, k);
		}
	}

	private int sort(int[] nums, int L, int R, int index) {
		this.swap(nums, index, R);
		int num = nums[R];
		int p = L;
		for (int i = L; i < R; i++) {
			if (nums[i] <= num) {
				this.swap(nums, p++, i);
			}
		}
		this.swap(nums, p, R);
		return p;
	}

	private void swap(int[] nums, int index, int r) {
		int tmp = nums[index];
		nums[index] = nums[r];
		nums[r] = tmp;
	}

	@Override
	public void debug4() {
//		[[980,476,644,56],[644,140,812,308],[812,812,896,560],[728,476,56,812]]
//				84
		H.compare(3780, this.minOperations(
				H.str2array1("[[980,476,644,56],[644,140,812,308],[812,812,896,560],[728,476,56,812]]"), 1));
		H.compare(5, this.minOperations(H.str2array1("[[1,5],[2,3]]"), 1));
		H.compare(45, this.minOperations(
				H.str2array1("[[980,476,644,56],[644,140,812,308],[812,812,896,560],[728,476,56,812]]"), 84));
		H.compare(4, this.minOperations(H.str2array1("[[2,4],[6,8]]"), 2));
		H.compare(-1, this.minOperations(H.str2array1("[[1,2],[3,4]]"), 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
